package simple;

/**
 *{@link
 * https://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec?tpId=188&&tqId=38556&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking}
 *
 *
 描述
 假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
 1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
 2.如果不能获取到任何利润，请返回0
 3.假设买入卖出均无手续费

 数据范围： 0 \le n \le 10000 , 0 \le val \le 100000≤n≤10000,0≤val≤10000
 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 示例1
 输入：
 [8,9,2,5,4,7,1]
 返回值：
 5
 说明：
 在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。
 *
 * @author WangZhiJian
 * @since 2022/1/4
 */
public class 买卖股票的最好时机一 {
    /**
     * 每天交易的最优解为 当前值减去之前的最小值,即为当天的最优解
     *
     *
     * @param prices int整型一维数组
     * 运行时间：26ms
     * 超过31.79% 用Java提交的代码
     * 占用内存：10216KB
     * 超过25.90%用Java提交的代码
     */
    public static int maxProfit (int[] prices) {
        if(prices == null || prices.length == 0)
            return 0;
        int minPrice = prices[0];
        int bestRes = 0;

        for (int i = 1; i < prices.length; i++) {
            if(bestRes < prices[i] - minPrice)
                bestRes = prices[i] - minPrice;
            if(minPrice > prices[i])
                minPrice = prices[i];
        }
        return bestRes;
    }



    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{8, 9, 2, 5, 4, 7, 1}));
    }
}
